/*
 * @lc app=leetcode.cn id=1670 lang=java
 *
 * [1670] 设计前中后队列
 */

// @lc code=start
class FrontMiddleBackQueue {

    DeQueue left;
    DeQueue right;

    public FrontMiddleBackQueue() {
        left = new DeQueue();
        right = new DeQueue();
    }
    
    public void pushFront(int val) {
        left.pushFront(val);
        update();

        // System.out.println("pushFront:"+toString());
    }
    
    public void pushMiddle(int val) {
        // System.out.println("pushMiddle:"+val+",left.count："+left.count+",right.count:"+right.count);
        if(left.count == right.count){
            right.pushFront(val);
        }
        else if(left.count < right.count){
            left.pushBack(val);
        }
        else if(right.count < left.count){
            right.pushBack(val);
        }        
        // System.out.println("pushMiddle:"+toString());
    }
    
    public void pushBack(int val) {
        right.pushBack(val);
        update();
        // System.out.println("pushBack:"+toString());
    }
    
    public int popFront() {
        int res;
        if(!left.isEmpty()) res = left.popFront();
        else if(!right.isEmpty()) res = right.popFront();
        else res = -1;
        update();
        // System.out.println("popFront.res:"+res+"..."+toString());
        return res;
    }
    
    public int popMiddle() {
        // System.out.println("popMiddle:left.count："+left.count+",right.count:"+right.count+",left.count==right.count:"+(left.count==right.count));
        int res = -1;
        //相等时，优先从左弹出
        if(left.count==right.count){
            res = left.popBack();
        }
        else if(right.count > left.count){
            res = right.popFront();
        }
        else if(left.count > right.count){
            res = left.popBack();
        }
        // System.out.println("popMiddle.res:"+res+"..."+toString());
        return res;
    }
    
    public int popBack() {
        int res;
        if(!right.isEmpty()) res = right.popBack();
        else if(!left.isEmpty()) res = left.popBack();
        else res = -1;
        update();
        // System.out.println("popBack.res:"+res+"..."+toString());
        return res;
    }
    //update 以及 popMiddle都是为了使队列按要求的样子存储或者出队
    public void update() {
        //保证左 <= 右
        while(left.count > right.count){
            right.pushFront( left.popBack() );
        }
        //保证右超过左 不多于一个
        while(right.count - left.count > 1){
            left.pushBack( right.popFront() );
        }
    }
    public String toString(){
        return dequeueToString(left)+"|"+dequeueToString(right);
    }
    public String dequeueToString(DeQueue dequeue){
        if(null == dequeue.head){
            return null;
        }
        StringBuffer sb = new StringBuffer();

        ListNode node = dequeue.head;

        while(null != node){
            sb.append(":"+node.val+":");
            node = node.next;
        }
        return sb.toString();
    }

    //双端队列
    class DeQueue{
        ListNode head;//虚头结点
        ListNode tail;//虚尾结点
        int count = 0;
        DeQueue(){
            head = new ListNode();
            tail = new ListNode();

            head.next = tail;
            tail.pre = head;
        }
        public void pushBack(int val){
            tail.insertPre(new ListNode(val));
            count ++;
        }
        public void pushFront(int val){
            head.inserNext(new ListNode(val));
            count ++;
        }
        public int popBack(){
            if(isEmpty()) return -1;
            int poped = tail.pre.val;
            tail.deletePre();
            count --;
            return poped;
        }
        public int popFront(){
            if(isEmpty()) return -1;
            int poped = head.next.val;
            head.deleteNext();
            count --;
            return poped;
        }
        public boolean isEmpty(){
            return head.next == tail;
        }
    }


    //双向链表节点
    class ListNode{
        int val;
        ListNode next;
        ListNode pre;

        public ListNode(){}
        public ListNode(int val){
            this.val = val;
        }
        public void inserNext(ListNode node){
            //将node放进去
            node.pre = this;
            node.next = this.next;

            //整理node相邻的两个节点
            //下面现行的顺序不能换，换了，this.next.pre的指向就不一样了
            if(null != this.next) this.next.pre = node;
            this.next = node;
        }
        public void insertPre(ListNode node){
            //将node放进去
            node.pre = this.pre;
            node.next = this;

            //整理node相邻的两个节点
            //下面现行的顺序不能换，换了，this.pre.next的指向就不一样了
            if(null!=this.pre) this.pre.next = node;
            this.pre = node;
        }
        public void deleteNext(){
            if(null == this.next) return ;

            if(null!=this.next.next) this.next.next.pre = this;
            this.next = this.next.next;
        }
        public void deletePre(){
            if(null == this.pre) return;

            if(null != this.pre.pre) this.pre.pre.next = this;
            this.pre = this.pre.pre;
        }
    }
}

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * FrontMiddleBackQueue obj = new FrontMiddleBackQueue();
 * obj.pushFront(val);
 * obj.pushMiddle(val);
 * obj.pushBack(val);
 * int param_4 = obj.popFront();
 * int param_5 = obj.popMiddle();
 * int param_6 = obj.popBack();
 */
// @lc code=end

